package 二叉树的层序遍历;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

/**
 * @author: zhengtao
 * @description: 填充每个节点的下一个右侧节点指针 II
 * @version: 1.0
 * @date: 2022/10/29  15:17
 */
public class Demo117 {

// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};

    public Node connect(Node root) {
        Queue<Node> queue=new ArrayDeque<>();

        if(root!=null){
            queue.add(root);
        }

        while (!queue.isEmpty()){
            int size = queue.size();
            List<Integer> temp=new ArrayList<>();
            while (size-->0){
                //出队列
                Node poll = queue.poll();
                //本层最后一个节点，指向null
                if(size==0){
                    poll.next=null;
                }else {
                    //不是最后一个节点，则指向下一个节点
                    poll.next=queue.peek();
                }
                if(poll.left!=null){
                    queue.add(poll.left);
                }
                if(poll.right!=null){
                    queue.add(poll.right);
                }
            }
        }
        return root;
    }
}
